#ifndef LINKED_SORT_H_
#define LINKED_SORT_H_

/**
 * @file LinkedSort.h
 */

#include <algorithm>
#include <utility>
#include <vector>

namespace spectClean {

/**
 * @class LinkedSort
 * @brief
 * @details
 */

class LinkedSort
{
    public:
        LinkedSort() {}

        virtual ~LinkedSort() {}

        template <typename T1, typename T2>
        static void lSort(std::vector<T1>& values, std::vector<T2>& linked1);

    public:
        /// Sort values and return sorted values and corresponding indices.
        template <typename T>
        static void sortIndices(std::vector<T> & values, std::vector<unsigned> & indices);

        /// Reorder values based on vector of indices.
        template <typename T>
        static void reorder(std::vector<T> & values, const std::vector<unsigned> & indices);

    private:
        /// Comparison function for sorting indices.
        template <typename T>
        static bool _compare(const std::pair<unsigned, T>& l, const std::pair<unsigned, T>& r);
};


//-----------------------------------------------------------------------------
template <typename T1, typename T2>
void LinkedSort::lSort(std::vector<T1>& values, std::vector<T2>& linked1)
{
    std::vector<unsigned> indices(values.size());
    sortIndices<T1>(values, indices);
    reorder<T2>(linked1, indices);
}



/// Sort values and return sorted values and corresponding indices.
template <typename T>
void LinkedSort::sortIndices(std::vector<T>& values, std::vector<unsigned>& indices)
{
    std::vector<std::pair<unsigned, T> > temp(values.size());

    for (unsigned i = 0; i < values.size(); ++i)
        temp[i] = std::pair<unsigned, T>(i, values[i]);

    std::sort(temp.begin(), temp.end(), _compare<T>);

    for (unsigned i = 0; i < values.size(); ++i) {
        indices[i] = temp[i].first;
        values[i] = temp[i].second;
    }
}

/// Reorder values based on vector of indices.
template <typename T>
void LinkedSort::reorder(std::vector<T>& values, const std::vector<unsigned>& indices)
{
    std::vector<T> temp(values.size());
    for (unsigned i = 0; i < values.size(); ++i)
        temp[i] = values[indices[i]];
    values = temp;
}

/// Comparison function for sorting indices.
template <typename T>
bool LinkedSort::_compare(const std::pair<unsigned, T>& l, const std::pair<unsigned, T>& r)
{
    return l.second < r.second;
}

} // namespace spectClean
#endif // LINKED_SORT_H_
